home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
The X-Philes (2nd Revision)
/
The X-Philes Number 1 (1995).iso
/
xphiles
/
hp48hor2
/
bogosort.doc
< prev
next >
Wrap
Text File
|
1995-03-31
|
3KB
|
61 lines
(Comp.sys.hp48)
Item: 595 by akcs.joehorn@hpcvbbs.cv.hp.com
Author: [Joseph K. Horn]
Subj: Bogo-Sort
Keyw: bogosort bogus stupid blond sort algorithm
Date: Sat Feb 08 1992
** PROGRAMMER'S RECREATION DEPARTMENT **
According to The Jargon File:
BOGO-SORT: n. (var. `stupid-sort') The archetypical perversely
awful algorithm (as opposed to {bubble sort}, which is merely the
generic *bad* algorithm). Bogo-sort is equivalent to throwing a
deck of cards in the air, picking them up, then testing whether
they are in order. If not, repeat. Used as a sort of canonical
example of awfulness. Usage: when one is looking at a program and
sees a dumb algorithm, one might say, "Oh, I see, this program uses
bogo-sort." Compare {bogus}.
So, here it is.
INPUT: List of real numbers to be sorted (with 2 or more elements).
OUTPUT: Bogo-sorted list (eventually...).
%%HP: T(3);
@ BOGOSORT, aka STUPID-SORT and BLOND-SORT
\<< 1 CF
DO OBJ\-> { } SWAP 1 @ shuffle the list
FOR j RAND j * CEIL 1 + ROLL + -1
STEP
UNTIL DUP OBJ\-> 2 SWAP @ until it's in order
START OVER < { 1 SF } IFT
NEXT DROP 1 FC?C
END
\>>
The otherwise thorough "Art of Computer Programming: Sorting and
Searching" by Donald Knuth is deafeningly silent regarding the
bogo-sort algorithm. Bob Wilson of Wichita, Kansas, says that it
would take n! iterations on the average; empirical evidence agrees.
But Harry Bertucelli says it's an exponential function of n. Hmm.
Not that it matter much. Very low I.Q.'s (like very high I.Q.'s)
are very hard to measure precisely...
In any case, Kevin Jessup points out that this ought to be rewritten
in machine language because "We all know that algorithm efficiency is
not important at the assembly level." ;-)
BTW, the astute codophile (that's a lover of code, not of cod) will
have already noticed (unlike the rest of you lugs to whom it must now
be pointed out) that the program above first shuffles the list, then
tests its ordinality (sortedness?). He xor she may object that it
would certainly be better to test first, thereby catching the case of
pre-sorted lists. Ah, but that would be blemishing the face of this
blissfully idiotic algorithm with a hint of intelligence. And
algorithms, like friends, are the most fun when they're really smart
or really stupid.
-jkh- EQU akcs.joehorn@hpcvbbs.cv.hp.com